package linkedlist;

import java.util.Stack;
import java.util.logging.Logger;

/**
 * 作者：吴超
 * 邮箱：wuchao_19931120@163.com
 * 时间：2021-10-20
 * 描述：单向链表的增删改查操作demo
 */

class HeroNode{

    public int num;
    public String name;
    public String nickName;
    public HeroNode next;

    public HeroNode(int aNum, String aName, String aNickName){

        this.num = aNum;
        this.name = aName;
        this.nickName = aNickName;

    }

    // 重写了toString方法，以后print这个实例的时候，就会按照如下格式显示
    @Override
    public String toString() {
        return "HeroNode{" +
                "num=" + num +
                ", name='" + name + '\'' +
                ", nickName='" + nickName + '\'' +
                "} ";
    }

}


class SingleLinkedList{

    private final HeroNode head;

//    private final HeroNode head = new HeroNode(0,"","");


    public SingleLinkedList(HeroNode ahead) {
        this.head = ahead;
    }

    public HeroNode getHead() {
        return this.head;
    }

    // 直接在链表后面添加，不考虑顺序
    public void addAppend(HeroNode heroNode){
        HeroNode tmp = head;
        while (tmp.next != null) {
            tmp = tmp.next;
        }
        tmp.next = heroNode;
    }


    // 添加会按照num的顺序进行
    // 代码值得借鉴的思路：1.先判断所有情况，然后跳出 2.跳出后进行操作 3.设置flag，判断特殊情况是否进行操作。
    public void addOrderByNum(HeroNode heroNode){
        HeroNode tmp = head;
        boolean flag = false;
        // 先找到tmp的位置，然后tmp后面的位置就可以插入新的节点
        while(true){
            if(tmp.next == null){
                break;
            }else if(tmp.next.num > heroNode.num){
                break;
            }else if(tmp.next.num == heroNode.num){
                System.out.println("已经存在 " + heroNode.num + " , 不能在重复插入添加！！！");
                flag = true;
                break;
            }else{
                tmp = tmp.next;
            }
        }
        // 如果没有重复的，那就在tmp后面插入
        if(!flag){
            heroNode.next = tmp.next;
            tmp.next = heroNode;
        }

    }

    // 按照num对节点进行修改，和上面同样的思路，先找到跳出的条件，然后根据flag是否为true进行操作
    public void update(HeroNode heroNode){
        HeroNode tmp = head;
        boolean flag = false;
        while (true){
            if(tmp.next == null){
                break;
            }else if(tmp.num == heroNode.num){
                flag = true;
                break;
            }else {
                tmp = tmp.next;
            }
        }
        if(flag){
            tmp.name = heroNode.name;
            tmp.nickName = heroNode.nickName;
        }else{
            System.out.println("没有 num 为: " + heroNode.num + " 的节点进行更新！！");
        }

    }

    // 按照num删除节点
    public void delete(int num){
        HeroNode tmp = head;
        boolean flag = false;
        while(true){
            if(tmp.next == null){
                break;
            }else if(tmp.next.num == num){
                flag = true;
                break;
            }else{
                tmp = tmp.next;
            }
        }
        if(flag){
            tmp.next = tmp.next.next;
        }else{
            System.out.println("没有 num 为: " + num + " 的节点进行删除！！");
        }
    }


    // 统计节点的有效个数，不包含头节点
    public static int getNumOfSingelList(HeroNode head){
        if(head.next == null){
            System.out.println("这是个空链表！！！");
            return 0;
        }
        HeroNode cur = head.next;
        int numOfList = 1;
        while (cur.next != null){
            numOfList++;
            cur = cur.next;
        }
        System.out.println("链表的长度为： " + numOfList + " !");
        return numOfList;
    }


    // 查找链表总的倒数第k个节点
    public static HeroNode findRecKnode(HeroNode head,int K){
        if(head.next == null){
            System.out.println("这是个空链表，找到不到倒数第 " + K + " 个节点！");
            return null;
        }
        if(K > getNumOfSingelList(head) || K <= 0){
            System.out.println("找不到倒数第 " + K + " 个节点！");
            return null;
        }
        int target = getNumOfSingelList(head) - K;
        HeroNode cur = head.next;
        for(int i=0;i<target;i++){
            cur = cur.next;
        }
        return cur;
    }


    // 反转单链表
    public static HeroNode reverseSingleList(HeroNode head){
        if(head.next == null){
            return null;
        }
        if(head.next.next == null){
            return head.next;
        }
        HeroNode oldHead = head.next;
//        HeroNode newTail = new HeroNode(0,"","");
        HeroNode newTail = null;
        while(oldHead != null){
            HeroNode tmp = oldHead.next;
            oldHead.next = newTail;
            newTail = oldHead;
            oldHead = tmp;
        }
        return newTail;
    }


    // 逆序打印单向链表，不改变原来的链表结构。使用栈
    public static void reversePrint(HeroNode head){
        if(head.next == null){
            return;
        }
        Stack<HeroNode> node_stack = new Stack<>();
        HeroNode cur = head.next;
        while (cur != null){
            node_stack.push(cur);
            cur = cur.next;
        }
        while (node_stack.size() > 0){
            System.out.println(node_stack.pop());
        }
    }


    public void showNodes(){
        if(head.next == null){
            System.out.println("链表为空！");
            return;
        }
        HeroNode tmp = head;
        while(tmp != null){
            System.out.println(tmp);
            tmp = tmp.next;

        }
    }

}


public class SingleLinkedListDemo {

    public static void main(String[] args){
        SingleLinkedList singleList = new SingleLinkedList(new HeroNode(0,"",""));

        HeroNode node1 = new HeroNode(1,"宋江","及时雨");
        HeroNode node2 = new HeroNode(2,"卢俊义","玉麒麟");
        HeroNode node3 = new HeroNode(3,"吴用","智多星");
        HeroNode node4 = new HeroNode(4,"林冲","豹子头");

        singleList.addAppend(node1);
        singleList.addAppend(node2);
        singleList.addAppend(node3);
        singleList.addAppend(node4);
        System.out.println("------------------");
        singleList.showNodes();
//        HeroNode reverseHead = SingleLinkedList.reverseSingleList(singleList.getHead());
//        System.out.println(reverseHead);
//        SingleLinkedList singleList_reverse = new SingleLinkedList(reverseHead);
//        singleList_reverse.showNodes();
        System.out.println("------------------");
        SingleLinkedList.reversePrint(singleList.getHead());


//        singleList.addOrderByNum(node1);
//        singleList.addOrderByNum(node4);
//        singleList.addOrderByNum(node2);
////        singleList.addOrderByNum(node1);
//        singleList.addOrderByNum(node3);

//        singleList.update(new HeroNode(3,"小吴","智多星呀~~"));
//        singleList.update(new HeroNode(10,"小吴","智多星呀~~"));
//        singleList.delete(4);

//        SingleLinkedList.getNumOfSingelList(singleList.getHead());

//        System.out.println(SingleLinkedList.findRecKnode(singleList.getHead(),4));


//        singleList.showNodes();

    }
}
